#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define true 1
#define false 0
#define maxSize 100
#define vertex 6

typedef struct 
{
    char vexs[maxSize][3];  //顶点表
    int arcs[maxSize][maxSize];  //邻接矩阵
    int vexNum,arcNum;  // 图的点数、边数
}AMGraph;

typedef struct  // 保存边的信息 
{
    int index;   // 结点位置
    int endEdge;  // 结尾边的位置
    int weight;
}versInfo;   

typedef struct 
{
    int* base;  //动态分配的内存空间
    int tail;   // 尾指针
}SqQueue;

int Location(AMGraph* graph,char* c)
{
    for(int i=0;i<graph->vexNum;i++)
    {
        if((graph->vexs[i][0]==c[0])&&(graph->vexs[i][1]==c[1]))
        {
            return i;
        }
    }
    return -1;
}

void creatUNM(AMGraph* graph,int countX)
{
    //countx 为节点的个数
    char buff[10];
    int count=0;
    FILE* f=fopen("./ax2.txt","r");
    
    while(fgets(buff,10,f)!=NULL)
    {
        count++;
    }
    fseek(f,0,SEEK_SET);
    graph->vexNum=countX;
    graph->arcNum=count-countX;

    for(int i=0;i<countX;i++)
    {
        fgets(buff,10,f);
        graph->vexs[i][0]=buff[0];  //载入顶点信息
        graph->vexs[i][1]=buff[1]; 
        graph->vexs[i][2]='\0';
    }
    for(int i=0;i<maxSize;i++)
    {
        for(int j=0;j<maxSize;j++)
        {
            graph->arcs[i][j]=-1;  // 邻接矩阵初始化
        }
    }

    int v1,v2;   // 临时记录两个顶点的位置信息
    char chs1[2],chs2[2];
    for(int i=0;i<(count-countX);i++)
    {
        fgets(buff,10,f);
        chs1[0]=buff[0];
        chs1[1]=buff[1];
        chs2[0]=buff[3];
        chs2[1]=buff[4];       
        v1=Location(graph,chs1);
        v2=Location(graph,chs2);

        // 记录边的信息
        graph->arcs[v1][v2]=buff[6]-'0';
        graph->arcs[v2][v1]=buff[6]-'0'; 
    }
    fclose(f);
}

void showMatrix(AMGraph* graph)
{
    for(int i=0;i<graph->vexNum;i++)
    {
        for(int j=0;j<graph->vexNum;j++)
        {
            printf("%d\t",graph->arcs[i][j]);
        }
        printf("\n");
    }
}

void showVertex(AMGraph* graph)
{
    for(int i=0;i<graph->vexNum;i++)
    {
        printf("%s\n",graph->vexs[i]);
    }
}

// 深度优先遍历
void deepSearch(AMGraph* graph,int index,int* Visited)
{
    printf("%s\t",graph->vexs[index]);
    Visited[index]=1;

    for(int i=0;i<graph->vexNum;i++)
    {
        if((graph->arcs[index][i]!=-1)&&(Visited[i]!=1))
        {
            deepSearch(graph,i,Visited);
        }
    }
}

int juadeEqual(AMGraph* graph,char chs[vertex][3])
{
    // 判断顶点是否相等
    int count=0;
    for(int i=0;i<vertex;i++)
    {
        int x=0;
        for(int j=0;j<3;j++)
        {
            if(graph->vexs[i][j]==chs[i][j])
                x++;
        }
        if(x==3)
            count++;
    }
    if(count==vertex)
        return true;
    else
        return false;
}
// 堆栈的简单实现
int IntStackpoint=-1;
void IntStackPush(int* chs,int c)
{
    chs[++IntStackpoint]=c;
}
int IntStackPop(int* chs)
{
    return chs[IntStackpoint--];
}
int IntStackEmpty(int* chs)
{
    if(IntStackpoint==-1)
        return true;
    else
        return false;
}

// 判断边的结尾顶点是否在集合中
int judgeEdgeINSet(char chs[vertex][3],int index)
{
    if(chs[index][0]=='V')
        return true;
    else
        return false;
}

void initPrimArcs(int PrimArcs[vertex][vertex])
{
    for(int i=0;i<vertex;i++)
    {
        for(int j=0;j<vertex;j++)
        {
            PrimArcs[i][j]=-1;
        }
    }
}
int** PrimMiniSpan(AMGraph* graph,int index)
{
    //创建一个顶点集合，一个边集合
    char Primvertexs[vertex][3]={{'\0'}};// 顶点集合
    int PrimArcs[vertex][vertex];  // 边集合
    initPrimArcs(PrimArcs);
    int IntStack[vertex];  // 堆栈数组
    //将开始的顶点加入到顶点集合中
    strcpy(Primvertexs[index],graph->vexs[index]);
    while(!juadeEqual(graph,Primvertexs))  //while 循环，当顶点集合不为空
    {
        // 找到存在的点，加入堆栈之中,堆栈只需存顶点位置的索引
        for(int i=0;i<vertex;i++)
        {
            if(Primvertexs[i][0]=='V')
            {
                IntStackPush(IntStack,Location(graph,Primvertexs[i]));
            }
        }
        versInfo info;
        info.weight=-1;
        while(!IntStackEmpty(IntStack))
        {
            //将堆栈中的所有顶点不断出栈，遍历结点中所有的边
            int tempVertex=IntStackPop(IntStack);  // 临时顶点
            for(int i=0;i<vertex;i++)
            {
                //存在边，结尾边不在顶点集合中
                if((graph->arcs[tempVertex][i]!=-1)&&(!judgeEdgeINSet(Primvertexs,i)))
                {
                    //初始化一个保存边的信息的结构体，存放第一个信息
                    if(info.weight==-1)
                    {
                        info.index=tempVertex;
                        info.endEdge=i;
                        info.weight=graph->arcs[tempVertex][i];
                    }
                    else
                    {
                        if(graph->arcs[tempVertex][i]<info.weight)
                        {
                            info.index=tempVertex;
                            info.endEdge=i;
                            info.weight=graph->arcs[tempVertex][i];
                        }
                    }
                }
            }
        }
        // 遍历结束，将顶点集合中的信息加入边集和中
        strcpy(Primvertexs[info.endEdge],graph->vexs[info.endEdge]);
        PrimArcs[info.index][info.endEdge]=info.weight;
        PrimArcs[info.endEdge][info.index]=info.weight;
    }
    printf("\n");
    for(int i=0;i<vertex;i++)
    {
        for(int j=0;j<vertex;j++)
        {
            printf("%d\t",PrimArcs[i][j]);
        }
        printf("\n");
    }
    int** result=(int**) malloc(vertex*(sizeof(int*)));
    for(int i=0;i<vertex;i++)
    {
        result[i]=(int*) malloc(vertex*(sizeof(int*)));
    }
    for(int i=0;i<vertex;i++)
    {
        for(int j=0;j<vertex;j++)
        {
            result[i][j]=PrimArcs[i][j];
        }
    }
    return result;
}

// 队列的初始化
SqQueue initQueue()
{
    int* basex=(int*) malloc(10*sizeof(int));
    SqQueue queue;
    queue.base=basex;
    for(int i=0;i<10;i++)
    {
        queue.base[i]=-1;
    }
    queue.tail=0;
    return queue;
}

// 队列的出队
int OutQueue(SqQueue* queue)
{
    int temp=-1;
    if(queue->base[0]!=-1)
    {
        temp=queue->base[0];
        for(int i=0;i<queue->tail-1;i++)
        {
            queue->base[i]=queue->base[i+1];
        }
        queue->tail--;
        queue->base[queue->tail]=-1;
    }
    return temp;
}

// 队列的入队
void joinQueue(SqQueue* queue,int data)
{
    queue->base[queue->tail++]=data;
}

//判断队列是否为空
int emptyQueue(SqQueue* queue)
{
    if(queue->tail==0)
    {
        return 1;
    }
    else
        return 0;
}

int countTuDegree(int KruskalArcs[vertex][vertex],int index)
{
    // 计算无向图中的度
    int sum=0;
    for(int i=0;i<vertex;i++)
    {
        if(KruskalArcs[index][i]!=-1)
            sum++;
    }
    return sum;
}

// 判断图中是否存在环
int judgeRing(int KruskalArcs[vertex][vertex])
{
    int tempKruskalArcs[vertex][vertex];  // 创建一个临时的邻接矩阵
    for(int i=0;i<vertex;i++)
    {
        for(int j=0;j<vertex;j++)
        {
            tempKruskalArcs[i][j]=KruskalArcs[i][j];
        }
    }

    int degree[vertex]={0};
    for(int i=0;i<vertex;i++)
    {
        // 保存所有结点的度
        degree[i]=countTuDegree(KruskalArcs,i);
    }

    SqQueue queue=initQueue(); // 队列初始化
    int n=0;  // 记录访问过的结点数
    for(int i=0;i<vertex;i++)   //将所有度 <= 1 的节点入队
    {
       if(countTuDegree(KruskalArcs,i)<=1)
       {
           joinQueue(&queue,i); 
           n++;
       }
    }
    while(!emptyQueue(&queue))
    {
        //当队列不空时进入循环，弹出队首元素
        int firstNode=OutQueue(&queue);
        // 把与队首元素相邻节点的度减一
        for(int i=0;i<vertex;i++)
        {
            if(tempKruskalArcs[firstNode][i]!=-1)
            {
                degree[i]-=1;
                if(degree[i]==1)
                {
                    joinQueue(&queue,i);
                    n++;
                }
            }
        }
    }
    if(n==vertex)
    {
        return false;
    }
    else
        return true;
}

void main()
{
    AMGraph graph;
    int visited[vertex]={0};
    creatUNM(&graph,vertex);

    showMatrix(&graph);
    showVertex(&graph);
    deepSearch(&graph,1,visited);
    int** xtemp =PrimMiniSpan(&graph,1);
    int tempGraph[vertex][vertex];
    for(int i=0;i<vertex;i++)
    {
        for(int j=0;j<vertex;j++)
        {
            tempGraph[i][j]=graph.arcs[i][j];
        }
    }
    int x=judgeRing(tempGraph);
    printf("%d\n",x);
}